package main

import "math"

// 53. 最大子数组和
func main() {

	arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	array := maxSubArray(arr)
	println(array)
}

func maxSubArray(nums []int) int {
	// 解法, 动态规划，逐个相加，如果前面的和大于最后一个值，则取和，否则取最后一个值
	// 假设值的结尾是i，如果i要最大，则要前面的和它相加更大，前面的又如何更大呢？逐个往前递推

	preMaxArray := make([]int, len(nums)+1)
	preMaxArray[0] = 0

	maxRes := math.MinInt

	for idx, num := range nums {
		sum := preMaxArray[idx] + num
		if sum > num {
			preMaxArray[idx+1] = sum
		} else {
			preMaxArray[idx+1] = num
		}
		if maxRes < preMaxArray[idx+1] {
			maxRes = preMaxArray[idx+1]
		}
	}

	return maxRes
}

// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
//子数组
//是数组中的一个连续部分。
//
//示例 1：
//
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
//示例 2：
//
//输入：nums = [1]
//输出：1
//示例 3：
//
//输入：nums = [5,4,-1,7,8]
//输出：23
//
//
//提示：
//
//1 <= nums.length <= 105
//-104 <= nums[i] <= 104
//
//进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
